
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1611. -- [Usaco2008 Feb]Meteor Shower流星雨 -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1611: [Usaco2008 Feb]Meteor Shower流星雨</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>373&nbsp;&nbsp;<span class=green>Solved: </span>166<br>[<a href='submitpage.php?id=1611'>Submit</a>][<a href='problemstatus.php?id=1611'>Status</a>][<a href='bbs.php?id=1611'>Discuss</a>]</center><h2>Description</h2><div class=content>去年偶们湖南遭受N年不遇到冰冻灾害，现在芙蓉哥哥则听说另一个骇人听闻的消息： 
一场流星雨即将袭击整个霸中，由于流星体积过大，它们无法在撞击到地面前燃烧殆尽， 
届时将会对它撞到的一切东西造成毁灭性的打击。很自然地，芙蓉哥哥开始担心自己的 
安全问题。以霸中至In型男名誉起誓，他一定要在被流星砸到前，到达一个安全的地方 
（也就是说，一块不会被任何流星砸到的土地）。如果将霸中放入一个直角坐标系中， 
芙蓉哥哥现在的位置是原点，并且，芙蓉哥哥不能踏上一块被流星砸过的土地。根据预 
报，一共有M颗流星(1 <= M <= 50,000)会坠落在霸中上，其中第i颗流星会在时刻 
T_i (0 <= T_i <= 1,000)砸在坐标为(X_i, Y_i) (0 <= X_i <= 300；0 <= Y_i <= 300) 
的格子里。流星的力量会将它所在的格子，以及周围4个相邻的格子都化为焦土，当然 
芙蓉哥哥也无法再在这些格子上行走。芙蓉哥哥在时刻0开始行动，它只能在第一象限中， 
平行于坐标轴行动，每1个时刻中，她能移动到相邻的（一般是4个）格子中的任意一个， 
当然目标格子要没有被烧焦才行。如果一个格子在时刻t被流星撞击或烧焦，那么芙蓉哥哥 
只能在t之前的时刻在这个格子里出现。请你计算一下，芙蓉哥哥最少需要多少时间才能到 
达一个安全的格子。 

</div><h2>Input</h2><div class=content>* 第1行: 1个正整数：M 
* 第2..M+1行: 第i+1行为3个用空格隔开的整数：X_i，Y_i，以及T_i 

</div><h2>Output</h2><div class=content>输出1个整数，即芙蓉哥哥逃生所花的最少时间。如果芙蓉哥哥无论如何都无法在流星雨中存活下来，输出-1 
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>4<br />
0 0 2<br />
2 1 2<br />
1 1 2<br />
0 3 5<br />
输入说明:<br />
    一共有4颗流星将坠落在霸中，它们落地点的坐标分别是(0, 0)，(2, 1)，(1, 1)<br />
以及(0, 3)，时刻分别为2，2，2，5。<br />
                                                                          <br />
       <br />
    t = 0                t = 2              t = 5<br />
5|. . . . . . .     5|. . . . . . .     5|. . . . . . .    <br />
4|. . . . . . .     4|. . . . . . .     4|# . . . . . . <br />
  * = 流星落点<br />
3|. . . . . . .     3|. . . . . . .     3|* # . . . . .  <br />
2|. . . . . . .     2|. # # . . . .     2|# # # . . . .   <br />
# = 行走禁区<br />
1|. . . . . . .     1|# * * # . . .     1|# # # # . . .   <br />
0|B . . . . . .     0|* # # . . . .     0|# # # . . . .   <br />
  --------------      --------------      -------------- <br />
  0 1 2 3 4 5 6       0 1 2 3 4 5 6       0 1 2 3 4 5 6 <br />
<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>5<br />
输出说明:<br />
    如果我们观察在t=5时的霸中，可以发现离芙蓉哥哥最近的安全的格子是<br />
(3,0)——不过由于早在第二颗流星落地时，芙蓉哥哥直接跑去(3,0)的路线就被封死了。<br />
离芙蓉哥哥第二近的安全格子为(4,0)，但它的情况也跟(3,0)一样。再接下来的格子就是在<br />
(0,5)-(5,0)这条直线上。在这些格子中，(0,5)，(1,4)以及(2,3)都能在5个单位时间内到达。<br />
<br />
       5|. . . . . . .   <br />
       4|. . . . . . .   <br />
       3|3 4 5 . . . .    某个合法的逃生方案中<br />
       2|2 . . . . . .    芙蓉哥哥每个时刻所在地点<br />
       1|1 . . . . . .   <br />
       0|0 . . . . . .   <br />
         -------------- <br />
         0 1 2 3 4 5 6  <br />
<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Silver'>Silver</a></p></div><center>[<a href='submitpage.php?id=1611'>Submit</a>][<a href='problemstatus.php?id=1611'>Status</a>][<a href='bbs.php?id=1611'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
